package com.lihepeng.leecode.sort;

import java.util.Arrays;

/**
 * 快速排序
 * 选择基准数字
 *
 * @author lihepeng
 */
public class QuickSort {

    public static void quickSort(int[] arrs, int low, int high) {
        int i, j, temp;
        if (low >= high) {
            return;
        }
        i = low;
        j = high;
        // 以最左边为基准位
        temp = arrs[low];
        while (i < j) {
            /**
             *   先看右边，依此向左边递减
             *   先从右边向左边找到小于基准数的数
             *   当右边的哨兵位置所在的数>基准数的时候
             *   继续从右向左找（同时j索引-1）
             *   找到之后跳出while循环
             */
            while (temp <= arrs[j] && i < j) {
                j--;
            }
            arrs[i] = arrs[j];
            // 看左边向右边增长
            while (temp >= arrs[i] && i < j) {
                i++;
            }
            arrs[j] = arrs[i];

        }
        arrs[i] = temp;
        quickSort(arrs, low, j - 1);
        quickSort(arrs, j + 1, high);
    }

    // 快速排序练习
    public void quickSort01(int[] arrs, int low, int heigh) {
        if (low > heigh) {
            return;
        }
        int index = getIndex(arrs, low, heigh);
        quickSort01(arrs, low, index - 1);
        quickSort01(arrs, index + 1, heigh);
    }

    // 寻找索引
    private int getIndex(int[] arrs, int low, int heigh) {
        int temp = arrs[low];
        while (low < heigh) {
            // 从后面向前推动 如果队尾的数大于等于基准数据的时候，向前挪动指针
            while (low < heigh && arrs[heigh] >= temp) {
                heigh--;
            }
            // 将队尾的元素赋值给基准元素
            arrs[low] = arrs[heigh];
            while (low < heigh && arrs[low] <= temp) {
                low++;
            }
            arrs[heigh] = arrs[low];
        }
        arrs[low] = temp;
        return low;
    }

    public void quickSortImpl(int[] arrs, int low, int heigh) {
        int i, j, temp;
        if (low > heigh) {
            return;
        }
    }

    /**
     * 第三次联系快速排序
     */
    public void quickSort02(int[] arrs) {
        // 寻找partion
        quickSort02(arrs, 0, arrs.length);
    }

    public void quickSort02(int[] arrs, int low, int heigth) {
        int partiation = getPartiation(arrs, 0, heigth);
        quickSort(arrs, low, partiation - 1);
        quickSort(arrs, partiation + 1, heigth);
    }

    private int getPartiation(int[] arrs, int low, int heigh) {
        int temp = arrs[low];
        while (low < heigh) {
            // 从队尾开始 如果 元素大于当前基准元素 交换元素
            while (low < heigh && arrs[heigh] >= temp) {
                heigh--;
            }
            // 将当前元素赋值给低位
            arrs[low] = arrs[heigh];
            while (low < heigh && arrs[low] < temp) {
                low++;
            }
            // 将当前元素赋值给高位
            arrs[heigh] = arrs[low];

        }
        arrs[low] = temp;
        return low;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
        QuickSort.quickSort(arr, 0, arr.length - 1);
        String s = Arrays.toString(arr);
        System.out.println(s);
    }

}
